# coding: utf-8
# 排列、组合实现 有点难 需要用到DFS(visit-deep-back)
# 组合需要用到visited列表，因为组合和顺序无关，只和是否存在有关系
# 排列组合算法总结(基于C++实现) https://blog.csdn.net/hf19931101/article/details/79452799

#全排列
def myPermutation(start,end,lst,res):
    """
    :type lst:list
    :type res:list
    :rtype None
    """
    #死胡同，输出结果
    if start==end:
        res.append(lst[:])
    #DFS：访问visit-深入deep-离开back
    for i  in range(start,end):
        #访问这个顶点
        lst[i],lst[start]=lst[start],lst[i]
        #深入
        myPermutation(start+1,end,lst,res)
        #离开这个顶点
        lst[i],lst[start]=lst[start],lst[i]

#部分排列
def partPermutation(pos,count,n,k,lst,res):
    """
    :type lst:list
    :type res:list
    """
    #死胡同1-数量够了
    if count==k:
        res.append(lst[0:count])
        return
    #死胡同2-到末尾了
    if pos==n:
        return
    #每个数都交换试试
    for i in range(pos,n):
        #visit
        lst[i],lst[pos]=lst[pos],lst[i]
        #deep
        partPermutation(pos+1,count+1,n,k,lst,res)
        #back
        lst[i],lst[pos]=lst[pos],lst[i]

#组合Cnk
def myComb(pos,count,n,k,lst,visited,res):
    """
    :type lst:list
    :type visited:list
    :type res:list
    """
    #死胡同
    if count==k:
        arr=[]
        for idx,val in enumerate(visited):
            if visited[idx]==1:
                arr.append(lst[idx])
        res.append(arr)
        return
    #死胡同
    if pos==n:
        return
    #包含这个数的情况
    visited[pos]=1
    myComb(pos+1,count+1,n,k,lst,visited,res)
    #不包含这个数的情况
    visited[pos]=0
    myComb(pos+1,count,n,k,lst,visited,res)

lst=[1,2,3,4]
result=[]
myPermutation(0,4,lst,result)
print("myPermutation:",result)
print(len(result))

result=[]
partPermutation(0,0,4,4,lst,result)
print("partPermutation:",result)
print(len(result))

visited=[0 for i in range(4)]
result=[]
myComb(0,0,4,2,lst,visited,result)
print("myComb:",result)

#使用内置方法
import itertools
lst=[1,2,3,4]
comb=list(itertools.combinations(lst,2))
print("内置方法-组合: {0}".format(comb))
permu=list(itertools.permutations(lst,4))
print("内置方法-排列: {0}".format(permu))
print(len(permu))
